#include "stdafx.h"

#include "Utils.h"

int minDstDP(int w[N][N]) {
	int states[N][N] = { 0 };
	//init states edge
	int sum = 0;
	for (int i = 0; i < N; i++) {
		sum += w[i][0];
		states[i][0] = sum;
	}
	sum = 0;
	for (int i = 0; i < N; i++) {
		sum += w[0][i];
		states[0][i] = sum;
	}

	for (int i = 1; i < N; i++) {
		for (int j = 1; j < N; j++) {
			states[i][j] = w[i][j] + MIN(states[i - 1][j], states[i][j - 1]);
		}
	}

	return states[N-1][N-1];
}